import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 673. 最长递增子序列的个数
 * 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 *
 * 注意 这个数列必须是 严格 递增的。
 */
public class FindNumberOfLIS {

    @Test
    public void test1() {
        Assertions.assertEquals(2, findNumberOfLIS(new int[]{1, 3, 5, 4, 7}));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(5, findNumberOfLIS(new int[]{2, 2, 2, 2, 2}));
    }


    @Test
    public void test3() {
        Assertions.assertEquals(3, findNumberOfLIS(new int[]{1, 2, 4, 3, 5, 4, 7, 2}));
    }

    public int findNumberOfLIS(int[] nums) {


        int[] incrementLength = new int[nums.length];
        int[] sequenceLengthCount = new int[nums.length];

        incrementLength[0] = 1;
        sequenceLengthCount[0] = 1;
        sequenceLengthCount[1] = 1;

        int maxLength = 0;
        for (int i = 1; i < nums.length; i++) {

            int maxIncrLength = 1;
            for (int j = 0; j < i; j++) {

                int incrLength = incrementLength[j];
                if (incrLength > 0 && nums[j] < nums[i]) {


                    if (incrLength + 1 > maxIncrLength) {
                        maxIncrLength = incrLength + 1;
                    }
                    sequenceLengthCount[incrLength + 1]++;
                }

            }
            sequenceLengthCount[1]++;
            incrementLength[i] = maxIncrLength;
            maxLength = Math.max(maxLength, maxIncrLength);

        }

        return sequenceLengthCount[maxLength];
    }
}
